/**
第二题：选取
【问题描述】
    给定n个整数a[i]，你需要求出有多少个从中选出k个的方案，使得这k个整数的和是质数。
    两种方案被视为不同，当且仅当存在一个i满足a[i]只在其中一种方案中被选出。
【输入格式】
    第一行两个整数n和k，第二行n个整数a[i]。
【输出格式】
    一行一个整数，表示从n个整数中选出k个数的和是质数的方案数。
【输入输出样例】
样例输入1
4 3
3 7 12 19

样例输出1
1

【数据范围约定】
    对于30%的数据，k=1；
    对于另40%的数据，n<=5；
    对于所有数据，1<=n<=20，k<n，1<=a[i]<=5000000。
**/
#include <bits/stdc++.h>

using namespace std;
int ans;

int iszs(int x) {
    for (int j = 2; j <= sqrt(x); j++) {
        if (x % j == 0) {
            return false;
        }
    }
    return true;
}

void pick(vector<int> &a, int k, vector<int> &v) {

    if (k == 0 || a.size() < k) return;

    if (k == 1) {

        // 从v里，把之前保存的元素，取出来打印、求和判断是否为素数
        cout << "找到新的组合:" << endl;
        for (int i = 0; i < a.size(); i++) {
            for (int x: v) {
                cout << x << " ";
            }
            cout << a[i] << " " << endl;

            //TODO: 这里我实现到了，把所有组合都找到，剩下的自己实现判断是否为素数吧！
            //打印结果如下：
            //找到新的组合:
            //1 2 3
            //1 2 4
            //1 2 5
            //找到新的组合:
            //1 3 4
            //1 3 5
            //找到新的组合:
            //1 4 5
            //找到新的组合:
            //2 3 4
            //2 3 5
            //找到新的组合:
            //2 4 5
            //找到新的组合:
            //3 4 5
        }

    } else {
        for (int i = 0; i < a.size(); i++) {

            int n = a[i];
            // 把 n 放入，已选容器 v 里
            v.push_back(n);

            // 将a复制成b
            // 这里要注意，只复制i后面的元素
            vector<int> b;
            for (int j = i + 1; j < a.size(); j++) {
                b.push_back(a[j]);
            }
            pick(b, k - 1, v);

            // 循环结束后，把 n 从 v 里删掉
            v.erase(v.end() - 1);
        }
    }
}

int main() {
    int n, k;

    // 保存所有组合
    vector<int> v;

    /*
    // 读入 n 和 k
    cin >> n >> k;
     int a[n];
    // 读入 n 个数字
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }*/

    n = 5;
    k = 3;

    std::vector<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);

    // 从a里，挑选k个元素，把中间过程保存在v里
    pick(a, k, v);
    return 0;
}
